function deepClone(src) {
    if (typeof src !== 'object' || src === null || src instanceof Date || src instanceof RegExp) {
        return src;
    }
    let cache = arguments[1] ? arguments[1] : new Map();
    let rtn = Array.isArray(src) ? [] : {};
    cache.set(src, rtn);
    for (const [key, val] of Object.entries(src)) {
        if (cache.has(val)) {
            rtn[key] = cache.get(val);
        } else {
            rtn[key] = deepClone(val, cache);
        }
    }
    return rtn;
}

/*  Sort.
    假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，
    即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；
    否则称为不稳定的。*/
class Sort {
    // 交换
    static swap(arr, i, j) {
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    static reverse(arr) {
        let i = 0,
            j = arr.length - 1;
        while (i < j) {
            this.swap(arr, i++, j--);
        }
        return arr;
    }
    // 冒泡排序，稳定
    static bubble(arr) {
        for (let i = arr.length - 1; i > 0; i--) {
            for (let j = 1; j <= i; j++) {
                if (arr[j - 1] > arr[j]) {
                    this.swap(arr, j - 1, j);
                }
            }
        }
        return arr;
    }
    // 选择排序，不稳定
    static selection(arr) {
        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    this.swap(arr, i , j);
                }
            }
        }
        return arr;
    }
    // 插入排序，稳定：对已经排列好的数列检测快
    static insertion(arr) {
        for (let i = 1; i < arr.length; i++) {
            let current = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];
                --j;
            }
            arr[j + 1] = current;
        }
        return arr;
    }
    // 快速排序，不稳定
    static quick(arr, low, high) {
        low = isFinite(low) ? low : 0,
        high = isFinite(high) ? high : arr.length - 1;
        if (low < high) {
            let f = this.quickPartition1(arr, low, high);
            this.quick(arr, low, f - 1);
            this.quick(arr, f + 1, high);
        }
        return arr;
    }
    static quickPartition1(arr, i, j) {
        let boundary = arr[i];
        let index = i;
        for (let n = i + 1; n <= j; n++){
            if (arr[n] < boundary) {
                this.swap(arr, ++index, n);
            }
        }
        this.swap(arr, index, i);
        return index;
    }
    static quickPartition2(arr, i, j) {
        let boundary = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= boundary) {
                --j;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] < boundary) {
                ++i;
            }
            arr[j] = arr[i];
        }
        arr[i] = boundary;
        return i;
    }
    // 堆排序，不稳定
    static heap(arr) {
        this.buildHeap(arr);
        for (let i = arr.length - 1; i > 0; i--) {
            this.swap(arr, i, 0);
            this.resetHeap(arr, 0, i);
        }
        return arr;
    }
    static buildHeap(arr) {
        // 构建大顶堆
        // p: var p = Math.floor((i - 1) / 2);
        // l: var l = 2i + 1;
        // r: var r = 2i + 2;
        for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
            this.resetHeap(arr, i, arr.length);
        }
        return arr;
    }
    static resetHeap(arr, i, size) {
        let l = 2 * i + 1,
            r = 2 * i + 2,
            largest = i;
        if (l < size && arr[largest] < arr[l]) {
            largest = l;
        }
        if (r < size && arr[largest] < arr[r]) {
            largest = r;
        }
        if (largest !== i) {
            this.swap(arr, largest, i);
            this.resetHeap(arr, largest, size);
        }
        return arr;
    }
    // 桶排序，稳定：适用于分布均匀的数列排序，bucketSize是期望每个桶的大小，不是实际每个桶的大小
    static bucket(arr, bucketSize = 5) {
        if (arr.length === 0) {
            return arr;
        }
        let minValue = arr[0],
            maxValue = arr[0];
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < minValue) {
                minValue = arr[i];
            } else if (arr[i] > maxValue) {
                maxValue = arr[i];
            }
        }
        let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
        let buckets = Array.from({length: bucketCount}).map(() => ([]));
        for (const item of arr) {
            buckets[Math.floor((item - minValue) / bucketSize)].push(item);
        }
        // console.log(buckets);
        arr.length = 0;
        for (const b of buckets) {
            arr.push(...this.insertion(b));
        }
        return arr;
    }
    // 归并排序，稳定，这是分治法(分而治之的思想)
    static merge(arr) {
        var len = arr.length;
        if (len < 2) {
            return arr;
        }
        let middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return this.mergePartition(this.merge(left), this.merge(right));
    }
    static mergePartition(left, right) {
        let rtn = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                rtn.push(left.shift());
            } else {
                rtn.push(right.shift());
            }
        }
        if (left.length > 0) {
            rtn.push(...left);
        } else if (right.length > 0) {
            rtn.push(...right);
        }
        return rtn;
    }
}

let arr = [4,5,6,1,2,3,9,8,7,0,100,5];
let rtn = Sort.merge(deepClone(arr));
console.log(rtn);
